/*
    城市交通路径规划系统
    实现过程说明

    这个程序的主要功能是为多个车辆在城市交通网络中规划最优路径，满足以下要求：
    1. 基础要求：为每辆车找到从起点到终点的最短路径，最小化所有车辆的总行驶时长。
    2. 高级要求：在路径规划过程中考虑道路的车流量限制，避免某条道路的同时行驶车辆数超过其最大承载能力。

    实现步骤：
    1. 读取输入数据，包括地点数量、车辆数量、道路长度矩阵、道路容量限制矩阵以及车辆的起点和终点。
    2. 对每辆车使用Dijkstra算法计算其最短路径，并记录总时长。
    3. 检查所有车辆的最短路径组合是否会导致任何道路的容量超限。
        a. 如果不超限，输出结果并结束程序。
        b. 如果超限，使用DFS枚举每辆车的所有可能路径，并尝试找到一个不超限的路径组合。
    4. 输出结果：
        - 如果Dijkstra方案不超限，按照指定格式输出每辆车的路径和总时长。
        - 如果Dijkstra方案超限，尝试所有走法后，如果找到一个不超限的组合，按指定格式输出路径和总时长。
        - 如果所有走法都超限，则输出相应提示信息。
*/

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
#include <map>

using namespace std;

// 用来表示一个非常大的数，用于Dijkstra算法
static const long long INF = 100000000;

// 记录路径信息：经过的节点和总时长
struct PathInfo {
    vector<int> pathNodes;    
    long long   totalTime;     
};

// 记录一个组合：每辆车选择的路径下标和总时长
struct Combo {
    vector<int> pathIndices;    
    long long   totalDuration;  
};

// 记录车辆在某条边上的行驶时间区间
struct EdgeInterval {
    long long startTime, endTime;  
};

// Dijkstra算法：找到从start到goal的最短路径及其总时长
pair<vector<int>, long long> findShortestPath(
    int N, 
    int start, 
    int goal,
    const vector<vector<pair<int, long long>>> &adj
){
    // 初始化距离数组和前驱数组
    vector<long long> distances(N+1, INF);
    vector<int> predecessors(N+1, -1);
    distances[start] = 0;

    // 小顶堆优先队列，按距离排序
    priority_queue< pair<long long, int>, 
                    vector<pair<long long, int>>, 
                    greater<pair<long long, int>> > priorityQ;
    priorityQ.push({0, start});

    while(!priorityQ.empty()){
        auto [currentDist, currentNode] = priorityQ.top();
        priorityQ.pop();
        // 如果当前距离不是最优的，跳过
        if(currentDist > distances[currentNode]) continue;

        // 如果到达目标点，结束
        if(currentNode == goal) break;

        // 更新邻接节点的距离
        for(auto &neighbor : adj[currentNode]){
            int neighborNode = neighbor.first;
            long long edgeWeight = neighbor.second;
            if(distances[currentNode] + edgeWeight < distances[neighborNode]){
                distances[neighborNode] = distances[currentNode] + edgeWeight;
                predecessors[neighborNode] = currentNode;
                priorityQ.push({distances[neighborNode], neighborNode});
            }
        }
    }

    // 如果目标点不可达，返回空路径
    if(distances[goal] >= INF){
        return {{}, INF};
    }

    // 重构路径
    vector<int> shortestPath;
    for(int cur = goal; cur != -1; cur = predecessors[cur]){
        shortestPath.push_back(cur);
    }
    reverse(shortestPath.begin(), shortestPath.end());
    return {shortestPath, distances[goal]};
}

// DFS算法：找到从当前点到目标点的所有简单路径
vector<PathInfo> allPossiblePaths; 

void findAllPaths(
    int current, 
    int destination,
    vector<bool> &isVisited,
    vector<int> &currentPath,
    long long accumulatedTime,
    const vector<vector<pair<int, long long>>> &adj
){
    isVisited[current] = true;
    currentPath.push_back(current);

    if(current == destination){
        // 到达终点，记录路径和总时长
        PathInfo pi;
        pi.pathNodes = currentPath;
        pi.totalTime  = accumulatedTime;
        allPossiblePaths.push_back(pi);
    } else {
        // 继续搜索邻接节点
        for(auto &neighbor : adj[current]){
            int neighborNode = neighbor.first;
            long long edgeWeight = neighbor.second;
            if(!isVisited[neighborNode]){
                findAllPaths(neighborNode, destination, isVisited, currentPath, accumulatedTime + edgeWeight, adj);
            }
        }
    }

    // 回溯
    currentPath.pop_back();
    isVisited[current] = false;
}

// 检查是否有道路的车流量超过容量限制
bool roadCapacityExceeded(
    const vector< vector<int> > &carPaths, // 每辆车的节点路径
    const vector<vector<pair<int, long long>>> &adj,  // 邻接表
    const vector<vector<int>> &roadCapacities,      // 道路容量限制
    int M
){
    // 记录每条道路的所有车辆行驶时间区间
    map< pair<int, int>, vector<EdgeInterval> > roadUsage;

    for(int car=1; car<=M; car++){
        const auto &path = carPaths[car];
        if(path.empty()) continue; // 跳过没有路径的车辆
        long long currentTime = 0;
        for(int i=0; i+1 < (int)path.size(); i++){
            int from = path[i];
            int to = path[i+1];
            // 查找边的长度
            long long roadLength = 0;
            for(auto &edge : adj[from]){
                if(edge.first == to){
                    roadLength = edge.second;
                    break;
                }
            }
            long long startTime = currentTime;
            long long endTime = currentTime + roadLength;
            roadUsage[{from, to}].push_back({startTime, endTime});
            currentTime = endTime; 
        }
    }

    // 对每条道路进行并发检测
    for(const auto &kv : roadUsage){
        auto road = kv.first;
        int from = road.first, to = road.second;
        int capacity = roadCapacities[from][to];
        // 如果容量不大于0，跳过
        if(capacity <= 0) continue; 
        const auto &intervals = kv.second;
        if(intervals.size() < 2) continue; // 不会并发

        // 生成进入和离开事件
        vector< pair<long long, int> > events;
        events.reserve(intervals.size()*2);
        for(auto &interval : intervals){
            events.emplace_back(interval.startTime, +1);
            events.emplace_back(interval.endTime, -1);
        }

        // 按时间排序，时间相同先离开再进入
        sort(events.begin(), events.end(), [](auto &a, auto &b){
            if(a.first != b.first) return a.first < b.first;
            return a.second < b.second;
        });

        long long ongoingCount = 0;
        for(auto &e : events){
            ongoingCount += e.second;
            if(ongoingCount > capacity){
                return true; // 会超限
            }
        }
    }
    return false; // 没有超限
}

// main函数 

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 读入地点数量N和车辆数量M
    int N, M;
    cin >> N >> M;

    // 读入道路长度矩阵，并构建邻接表
    // 使用邻接表 'adj' 来存储每条边的长度
    vector<vector<pair<int, long long>>> adj(N+1);
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            long long len; 
            cin >> len;
            if(len > 0){
                adj[i].emplace_back(j, len);
            }
        }
    }

    // 读入道路容量限制矩阵
    vector<vector<int>> roadCapacities(N+1, vector<int>(N+1, 0));
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            int flow; 
            cin >> flow;
            roadCapacities[i][j] = flow;
        }
    }

    // 读入每辆车的起点和终点
    vector<pair<int, int>> vehicles(M+1);
    for(int car=1; car<=M; car++){
        int s, t;
        cin >> s >> t;
        vehicles[car] = {s, t};
    }

    // (1) 首先: Dijkstra 方案 
    // 为每辆车跑一次 Dijkstra，得到最短路径
    long long pathCostSum = 0;
    vector<vector<int>> shortestPaths(M+1);

    bool allReachable = true; // 如果有车不可达则置false

    for(int car=1; car<=M; car++){
        auto [path, pathCost] = findShortestPath(N, vehicles[car].first, vehicles[car].second, adj);
        if(path.empty() || pathCost >= INF){
            // 表示不可达
            allReachable = false;
            continue;
        }
        shortestPaths[car] = path;
        pathCostSum += pathCost;
    }

    // 检测是否所有车辆都可达
    if(!allReachable){
        cout << "有车辆无法到达目的地.\n";
        return 0;
    }

    // 检测“Dijkstra方案” 是否超限
    bool exceedDij = roadCapacityExceeded(shortestPaths, adj, roadCapacities, M);
    if(!exceedDij){
        // 不会超限 => 按照指定格式输出路径和总时长
        for(int car=1; car<=M; car++){
            for(int nodeIdx=0; nodeIdx<(int)shortestPaths[car].size(); nodeIdx++){
                cout << shortestPaths[car][nodeIdx];
                if(nodeIdx+1 < (int)shortestPaths[car].size()) cout << " ";
            }
            cout << "\n";
        }
        cout << pathCostSum << "\n";
        return 0;
    }
    // 否则 => Dijkstra方案超限，继续找所有组合

    // (2) 为每辆车搜“所有可行路径” 
    vector<vector<PathInfo>> allPossiblePathsOfCar(M+1);
    for(int car=1; car<=M; car++){
        int s = vehicles[car].first;
        int t = vehicles[car].second;
        allPossiblePaths.clear();
        vector<bool> isVisited(N+1, false);
        vector<int> currentPath;
        findAllPaths(s, t, isVisited, currentPath, 0LL, adj);
        allPossiblePathsOfCar[car] = allPossiblePaths;
    }

    // (3) 枚举所有组合, 按总时长升序, 找第一个不超限 
    vector<Combo> combos;
    function<void(int, vector<int>&, long long)> makeCombos = 
    [&](int carIndex, vector<int> &pick, long long sumCost){
        if(carIndex > M){
            Combo c;
            c.pathIndices = pick; 
            c.totalDuration = sumCost;
            combos.push_back(c);
            return;
        }
        for(int pathIdx=0; pathIdx<(int)allPossiblePathsOfCar[carIndex].size(); pathIdx++){
            long long cost_i = allPossiblePathsOfCar[carIndex][pathIdx].totalTime;
            pick[carIndex] = pathIdx;
            makeCombos(carIndex+1, pick, sumCost + cost_i);
        }
    };

    vector<int> pick(M+1, -1);
    makeCombos(1, pick, 0LL);

    // 按总时长升序排序
    sort(combos.begin(), combos.end(), [](auto &a, auto &b){
        return a.totalDuration < b.totalDuration;
    });

    bool combinationFound = false;
    for(auto &c : combos){
        vector<vector<int>> candidatePaths(M+1);
        for(int car=1; car<=M; car++){
            int pathIdx = c.pathIndices[car];
            candidatePaths[car] = allPossiblePathsOfCar[car][pathIdx].pathNodes;
        }
        bool exceedFlag = roadCapacityExceeded(candidatePaths, adj, roadCapacities, M);
        if(!exceedFlag){
            for(int car=1; car<=M; car++){
                for(int nodeIdx=0; nodeIdx<(int)candidatePaths[car].size(); nodeIdx++){
                    cout << candidatePaths[car][nodeIdx];
                    if(nodeIdx+1 < (int)candidatePaths[car].size()) cout << " ";
                }
                cout << "\n";
            }
            cout << c.totalDuration << "\n";
            combinationFound = true;
            break;
        }
    }

    if(!combinationFound){
        cout << "所有走法都超出限流.\n";
    }

    return 0;
}
